The present invention relates generally to the field of digital computers and particularly to a circuit for resolving contention within a queuing system for use of a shared facility, such as a data bus to and from a common memory, among a plurality of system elements which collectively produce a random rate of request for access to the shared facility.
In digital computer systems and especially systems which have parallel processing capability or multiplexing communication channels, circuits have been developed to resolve simultaneous requests for use of a shared facility such as a data bus. Such circuits, commonly known as Bus Access Controllers, must establish the required priority hierarchy and a means for arbitrating simultaneous bus access requests. Since the arrival time for bus access requests is aperiodic, and at times will exceed the rate which the shared facility can service such requests, a queuing system is thus established. Request queuing requires that units which require fast bus access be given priority at the next request polling sequence.
When the request queue is empty, bus access will be granted to the next unit or units which make a request. In this case controls are required to eliminate ambiguity of access grant when multiple unit access requests are made simultaneously.
Approaches for solving contention for simultaneous access to a shared facility generally use a polling circuit where each request initiates a polling cycle. Such polling circuits fall into two general categories usually referred to as serial and parallel arbiters. In a serial arbiter the polling signal propagates through all the units coupled thereto and the first unit with a request outstanding blocks further propagation of the polling signal and initiates the desired use of the shared facility. Systems using such serial arbiters have slow arbitration speed but economy is achieved by having fewer circuits and control lines on the bus. This approach is quite useful for controlling asynchronous data transfers over a multiplexed bus, for example, but is not always suitable in environments requiring high speed access to the shared facility.
In attempting to improve access time and thereby data transfer capability over a common facility such as a data bus, priority schemes employing parallel arbiter circuits have been developed to grant access to the common facility, first to the unit having highest priority and thereafter to units of successively lower priority thereafter. Such circuit arrangements, however, typically require extensive backpanel signal interconnections and component counts in order to resolve priority amongst a plurality of requesting units. This increased number of circuits has given rise to higher manufacturing cost and has additionally given rise to some reduction in performance due to the fact that several logic circuit levels will be required to resolve contention amongst a plurality of units when the number of contending units becomes quite high.
Accordingly, it is the primary object of the present invention to provide an arbiter for resolving multiple simultaneous access requests for use of a common facility from a plurality of system components which have differing speed requirements for access to the common facility.
It is still a further objective of the present invention to provide an arbiter for resolving multiple simultaneous access requests to a common facility which maximizes performance of the system while keeping circuit costs and interconnection to a level normally found only in slower single level serial arbitration implementations.